package euler.p051_100;

import java.math.BigInteger;

import euler.MainEuler;
import euler.helper.NaturalHelper;

public class Euler066_i extends MainEuler {

    /*
        Consider quadratic Diophantine equations of the form:

        x^2 – D×y^2 = 1

        For example, when D=13, the minimal solution in x is 649^2 – 13×180^2 = 1.

        It can be assumed that there are no solutions in positive integers when D is square.

        By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

        3^2 – 2×2^2 = 1
        2^2 – 3×1^2 = 1
        9^2 – 5×4^2 = 1
        5^2 – 6×2^2 = 1
        8^2 – 7×3^2 = 1

        Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

        Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

     */
    public static void resolve() {

        int limite = 1000; //1000
        BigInteger maxX = BigInteger.ZERO;
        int bestD = 0;

        for (int D = 2; D <= limite; D++) {
            if (!esCuadrado(D)) {
                boolean terminar = false;
                for (BigInteger y = BigInteger.ONE; !terminar; y=y.add(BigInteger.ONE)) {
                    BigInteger xcuadrado = y.multiply(y).multiply(BigInteger.valueOf(D)).add(BigInteger.ONE);
                    BigInteger x = NaturalHelper.squareRoot(xcuadrado).toBigInteger();
                    if (x.multiply(x).compareTo(xcuadrado) == 0) {
                        terminar = true;

                        System.out.println(x + "^2 – " + D + "×" + y + "^2 = 1");

                        if (maxX.compareTo(x) < 0) {
                            maxX = x;
                            bestD = D;
                        }
                    }
                }
            }
        }

        System.out.println(bestD);
    }

    private static boolean esCuadrado(int n) {
        int m = (int)Math.sqrt(n);

        for (int i = m - 1; i < m + 1; i++) {
            if (i*i == n) {
                return true;
            }
        }
        return false;
    }

}
